1. Technical Field
This invention generally relates to computer data systems, and more specifically relates to an apparatus and methods for analyzing relationships of objects when all objects in combinations are required for problem resolution to determine which objects to place in a container (cache) to improve system performance.
2. Background Art
Computing which items are most advantageous to keep when not all items can fit within a given container constraint is known as a “knapsack” problem. Solutions to this problem are discussed in resources such as the book Knapsack Problems: Algorithms and Computer Implementations by Silvano Martello and Paolo Toth. This book and other published papers address the most efficient algorithms and various problems with existing algorithms in order to solve the problem of finding the correct subset of individual objects to add to a container within a given constraint. However, these references do not solve the problem of how to analyze the objects' relationships when individual objects alone are not the items to be added to the container. In these cases, it is a combination of individual objects that are required in the container for a search request, and by including one combination, other combinations become more advantageous to include.
Attribute caching in a computer directory server is a specific case where knapsack problems are encountered. A type of directory server common in the art is the Lightweight Directory Access Protocol (LDAP) directory. LDAP is an Internet protocol that is used by programs to look up information from an LDAP repository or directory. Thus, LDAP defines the “language” used by client programs to talk to LDAP servers which can store data in any type of repository. On the client side, a client may be an email program, a printer browser, or an address book. LDAP also defines permissions, set by the administrator to allow only certain people to access the data stored in the LDAP directory structure, and optionally keep certain data private. An LDAP schema is a way to describe the format and attributes of data in the server.
Some LDAP type directory servers have a feature known as attribute caching that allows server administrators to define a set of attributes to cache in memory as well as to configure the maximum amount of memory to use for this caching. These attributes are stored in database tables but continually accessing these tables to resolve LDAP searches requires excessive system resources, so the attributes are cached in memory to increase efficiency. If all attributes necessary for resolving an LDAP search are found in the attribute caches in memory, the search will be resolved quickly in memory by the directory server rather than using database queries against the database tables. Therefore, attribute caching is a performance enhancing feature of the directory server.
Attribute caching in the prior art is incredibly difficult to configure. The administrator needs to understand the types of searches done by all applications accessing the server. Even though the server reports which attributes were most frequently used in search filters, it simply cannot report the relationships between the attributes along with all the attributes required to resolve every type of search filter used in the applications and expect the administrator to configure it manually based on real-time usage.
Without a way to cache objects more efficiently when the individual objects are not the items to be added to the container (such as a memory cache), the computer industry will continue to suffer from inefficiency and poor performance.